1. Field of the Invention
The present invention relates to data transfer systems. In particular, the invention relates to an error-correcting method, an error-checking device, a decoding method and a decoder applied to a system for error correction and check of a multidimensional code such as a product code.
2. Description of the Background Art
Image information and the like containing a large amount of information are now recorded, reproduced and transmitted by digital signals in most instances. Accordingly, there arises an increased importance of error correction and error check in order to enhance the reliability of recorded information or transmitted information. Especially real-time recording and reproduction requires high-speed processing for correcting and checking any error in such a large amount of information.
A conventional data transfer system, for example, a recordable and reproducible magneto-optical disk device adds an error-correcting code formed of a product code to received data and stores the data on a recording medium.
The stored data is thereafter called by an error-correcting device as required and any error is corrected. Error check is then carried out by an error detecting code (hereinafter referred to as EDC) to confirm absence of errors, and the data is output to the outside.
In a reproduction-only optical disk device, stored data is similarly called as required by an error-correcting device where any error is corrected. Error check is thereafter performed by an error detecting code to confirm absence of errors. The data is then output to the outside.
Problems of Error Correction and Error Check
According to a conventional error-correcting method, data read from a DVD (Digital Versatile Disk) for example is temporarily stored in a buffer of an external semiconductor memory device such as a Synchronous Dynamic Random Access Memory (SDRAM. The data is then called by an error-correcting device to correct any error.
The DVD employs for example a product code constituted of data arranged in a rectangular shape to which error-correcting codes are added in two directions, i.e., the vertical direction (PO direction) and the horizontal direction (PI direction).
FIG. 32 shows a format of a conventional error-correcting product code for the DVD.
Here, one block refers to data formed of information data arranged in two-dimension in 172 bytes×192 rows to which horizontal 10-byte parity PI (error-correcting inter code) and vertical 16-byte parity PO (error-correcting outer code) are added. The horizontal and vertical directions are also called PI and PO directions respectively in FIG. 32.
FIG. 33 shows a relation between the error-correcting product code (error-correcting inter code and error-correcting outer code) in FIG. 32 and error detecting codes (EDC).
One block mentioned above is divided into sixteen sectors each consisting of data arrangement in 172 bytes×12 rows. One sector includes a 4-byte EDC at its end.
FIG. 34 shows data arrangement in one sector containing the error detecting code. The bits are numbered in descending order from the leading bit.
The one-sector data are arranged as data from bit data b16511 to bit data b0 and bit data b31 to b0 correspond to the EDC.
FIG. 35 is a schematic block diagram illustrating a first conventional structure for error correction and error check applied to the DVD data structured as discussed above.
Referring to FIG. 35, a basic decoding pattern follows the procedure for example described below.
1. An input signal is stored in a data buffer (SDRAM: Synchronous Dynamic Random Access Memory) 3024 via a data bus 3021, and a PI direction error-correcting circuit 3020 reads data in PI direction from data buffer 3024 to calculate a syndrome.
2. PI direction error-correcting circuit 3020 detects an error amount and an error position from the value of the PI direction syndrome to correct any error in the data stored in data buffer 3024.
3. A PO direction error-correcting circuit 3022 reads data in PO direction from data buffer 3024 to calculate a syndrome.
4. PO direction error-correcting circuit 3022 calculates an error amount and an error position from the value of the PO direction syndrome to correct any error in the data stored in data buffer 3024.
These processes are repeated to correct errors.
5. After the error correction is completed, an error-checking circuit 3023 reads the data from data buffer 3024 to confirm absence of errors by using error detecting codes.
A problem here in these processes is that the error correction and check takes a long time since, after error correction, data buffer (SDRAM) 3024 is accessed again for error check.
For example, in the structure shown in FIG. 35, only after error correction of data read from data buffer 3024 is completed, error-checking circuit 3023 reads the data from data buffer 3024. Relatively time-consuming data reading and writing from and to data buffer 3024 is carried out frequently, resulting in a longer time taken by the processes.
Japanese Patent Laying-Open No. 11-55129 for example discloses a method to overcome this problem.
FIG. 36 is a schematic block diagram illustrating a second conventional structure for error correction and error check disclosed in Japanese Patent Laying-Open No. 11-55129.
The error-correcting and checking device shown in FIG. 36 is structured to use a data bus shared by an error-correcting circuit and an error-checking circuit.
FIGS. 37, 38, 39 and 40 respectively show first to fourth models illustrating a general process followed by the error-correcting and checking device shown in FIG. 36.
In FIGS. 37 and 38, data to be error-checked are shown in a decreased number, i.e., 40 data (10 columns×4 rows) for the purpose of simplifying illustration.
Error check by means of the error-correcting and checking device shown in FIG. 36 is carried out in two stages.
In the first stage, data is read from a buffer 3034 for error correction in PI direction for example, and the data is transferred in the data arrangement order as shown in FIG. 37 to a DATA syndrome generating circuit 3036 to calculate a DATA syndrome.
The calculated DATA syndrome is stored in a memory device 3032.
In the first stage, in addition to the DATA syndrome calculation, an ERROR syndrome is calculated by using an error amount detected by a PI direction error-correcting circuit 3030 according to the data arrangement order shown in FIG. 37.
In the second stage, an error amount detected by a PO direction error-correcting circuit 3032 is further used to perform subsequent ERROR syndrome calculation according to the data arrangement order shown in FIG. 38.
Referring to FIG. 39, an exclusive-OR operation unit 3035 calculates the exclusive-OR of the two syndromes, DATA syndrome and ERROR syndrome, so as to determine a final check syndrome. Based on the check syndrome, a decision circuit 3031 judges results of error check.
The second-time data reading from data buffer 3034 for generating a check syndrome is thus unnecessary so that fast and parallel error correction and check processes are possible.
Further, in the calculation of the error-correction syndrome by PO direction error-correcting circuit 3032, if codewords in column 3 (COL3) have no. error, subsequent detection of an error amount and an error position is skipped. According to this, in the ERROR syndrome calculation, the speed of operation is enhanced by using offset values for the codewords without error as shown in FIG. 40.
However, this offset calculation requires, in ERROR syndrome generating circuit 3038, an operating circuit having at least three paths for syndrome calculation corresponding respectively to an operation proceeding through rows one by one in the vertical direction, an operation through columns from one column to the next column, and an operation through columns at every other columns. A problem then arises of increase in the circuit scale.
Problems of Syndrome Calculation
Other problems of syndrome calculation in the error-correcting operation are discussed below.
The conventional error-correcting system such as DVD uses a product code as described above having data arranged in the rectangular shape to which error-correcting codes are added in the vertical and horizontal directions.
FIG. 41 is a schematic block diagram showing a structure of a conventional error-correcting device 4000 for the error-correcting calculation as discussed above.
Referring to FIG. 41, in error-correcting device 4000, data read into an external memory 4021 undergoes error correction by an error-correcting circuit 4022.
Error-correcting circuit 4022 reads the data from external memory 4021 for correcting any error and then the data with its error corrected is written into external memory 4021 again.
After all errors are corrected, a descramble operation is performed by a descrambling circuit 4023.
Descrambling circuit 4023 reads the data from external memory 4021 to descramble the data and the descrambled data is written into external memory 4021 again.
Specifically, a basic decoding pattern follows the procedure below.
1. PI direction data is read from external memory (e.g. SDRAM) 4021 to calculate a syndrome.
2. An error amount and an error position are calculated from the syndrome value to correct any error on external memory 4021.
3. PO direction data is read from external memory 4021 to calculate a syndrome.
4. An error amount and an error position are calculated from the syndrome value to correct any error in data stored on external memory 4021.
These processes are repeated to accomplish error correction.
5. After this error correction, data (D′k: data produced by scrambling data Dk is hereinafter represented by D′k) is read from external memory. 4021 again to descramble the data by descrambling circuit 4023 according to the following expression.Dk=D′kExor Sk(k=0−2047)  (A1)
Here, S0 is supplied as an initial value by a table provided in advance. Further, data Sk derived from the following expressions is used to descramble data D′k.
                                                        T              0                        =                          {                                                                    7                    '                                    ⁢                  d0                                ,                S0                            }                                ⁢                                          ⁢                                          ⁢                                          ⁢                                    T                              n                +                1                                      [                          14              ⁢                              :                            ⁢              0                        ]                          ⁢                                                      (        A2        )                                                          ⁢                              =                          {                                                                    T                    n                                    [                                      13                    ⁢                                          :                                        ⁢                    1                                    ]                                ,                                  (                                                                                    T                        n                                            ⁡                                              [                        14                        ]                                                              ⁢                                                                                  ⁢                    Exor                    ⁢                                                                                  ⁢                                                                  T                        n                                            ⁡                                              [                        10                        ]                                                                              )                                            }                                ⁢                                          ⁢                                          ⁢                      (                          n              =                              0                ⁢                                  -                                ⁢                8                ×                2047                                      )                                              (        A3        )                                          S          k                =                              T                          8              ⁢              k                                [                      7            ⁢                          :                        ⁢            0                    ]                                    (        A4        )            
In expression (A2), “7′d0” means there are seven data “0” that are lined. Expression (A2) represents that seven “0” and S0 as the initial value are connected to form data To of 15 bits from the 14th bit to the 0th bit.
Expression (A3) represents that data Tn [13:0] from the 13th bit to the 0th bit in data Tn [14:0] generated in the n-th step is lined next to the exclusive-OR of the 14th bit data Tn [14] and the tenth bit data Tn [10] in data Tn [14:0] to generate in the (n+1)-th step data Tn+1[14:0] formed of 15-bit data from the 14th bit to the 0th bit.
Expression (A4) represents that in the data Tn [14:0] thus generated the data of the 7th bit to the 0th bit in the data T8k[14:0] formed in the 8-multiple-th step corresponds to data Sk.
The access to the external memory is enormous in the circuit structure shown in FIG. 41, which consumes a longer time and accordingly makes it difficult to enhance the speed of error correction and descrambling.
A conventional art for overcoming such a problem is described below.
FIG. 42 is a schematic block diagram showing a structure of an error-correcting device 5000 as such a conventional art that is disclosed in Japanese Patent Laying-Open No. 10-126279.
Referring to FIG. 42, for data read into an external memory 5031, syndrome calculation is performed by a syndrome operating circuit 5032 as a part of error-correcting calculation.
At the same time, the read data is sent to a descrambling circuit 5033 to be descrambled. The descrambled data is written into external memory 5031.
A syndrome determined by the syndrome calculation is supplied to an error amount calculating unit 5034 to calculate an error amount and an error position. Error amount calculating unit 5034 reads data corresponding to the error position from external memory 5031, corrects any error, and the data is written into external memory 5031 again.
Although this method reduces the access to the external memory approximately by two thirds, this reduction is not enough.
Further, the method considers nothing about the repeating processes specific to the product code. Therefore, efficient error correction/descrambling for the actual DVD and the like is difficult to achieve.
Specifically, error correction of the product code is generally performed in each of the directions (PO and PI directions) repeatedly. Here, syndrome calculation for performing error correction uses data before descrambling. If descrambling as shown in FIG. 42 is employed, data stored in external memory 5031 must be scrambled again in order to perform subsequent error correction repeatedly, resulting in increase in the calculation amount and circuit scale.
Problems of Euclidean Calculation
Problems of Euclidean calculation in the error-correcting operation are described below.
FIG. 43 is a schematic block diagram showing a structure of an error-correcting device 6000 in a conventional data transmission system, for example, a recordable and reproducible magneto-optical disk device.
Referring to FIG. 43, the data transmission system adds an error-correcting code formed of a product code to data to be recorded and stores the data on a recording medium. The data stored on the recording medium is then supplied as received data to error-correcting device 6000 as required and thereafter output to the outside after error correction.
Such a structure is employed not only in the recordable and reproducible magneto-optical disk device but also in a reproduction only optical disk device.
An error-correcting process is discussed below carried out in a DVD for example. The DVD employs error correction by a Reed-Solomon code (RS code) exhibiting a high correcting ability.
Received data called for transmission from a disk to error-correcting device 6000 is temporarily stored in a semiconductor memory device; specifically memory 6010 such as an SRAM (Static Random Access Memory). The data in memory 6010 is thereafter called for the error-correcting process in which the following procedure steps are successively followed.
The five steps below are generally employed for error correction using the Reed-Solomon code.
1. A syndrome calculating circuit 6020 calculates a syndrome from the received data.
2. A Euclidean calculating circuit 6030 determines an error locator polynomial and an error evaluator polynomial from that syndrome.
3. A Chien search circuit 6040 determines an error position from the error locator polynomial.
4. Chien search circuit 6040 determines an error amount from the error locator polynomial, error evaluator polynomial and error position.
5. An error-correcting circuit 6050 corrects any error using the error amount and position.
Regarding the error correction by the Reed-Solomon code having a high correction ability, a Euclidean method derived from the Euclidean algorithm is known that is used in step 2 above for determining the error locator polynomial and the error evaluator polynomial from the syndrome.
This Euclidean method is now described in detail below.
A reception polynomial r (x) of the received data described above is represented here by the expression below:r(x)=rn−1xn−1+rn−2xn−2+ . . . +r1x+r0  (B1)where n is a code length.
A syndrome polynomial determined by syndrome calculation is represented as below.S(x)=S2t−1x2t−1+S2t−2x2t−2+ . . . +S1x+S0  (B2)
                              S          j                =                              ∑            i                    ⁢                                    r              i                        ⁢                          α                              j                ×                i                                      ⁢                                                  ⁢                          (                                                i                  =                  0                                ,                                                                  ⁢                …                ⁢                                                                  ,                                  n                  -                  1                                ,                                  j                  =                  0                                ,                                                                  ⁢                …                ⁢                                                                  ,                                                      2                    ⁢                    t                                    -                  1                                            )                                                          (        B3        )            
In the expressions above, t denotes the number of correctable errors and α denotes the root of a primitive polynomial on GF(P). With respect to GF(28), roots in a root set of the primitive polynomial are expressed by 0, 1, α1, α2, . . . α6.
Error locator polynomial σ (x) is defined here by the following expression:
                              σ          ⁡                      (            x            )                          =                              ∏                          i              ∈              E                                                                      ⁢                                          ⁢                      (                          x              -                              α                                                      -                    1                                    ⁢                  i                                                      )                                              (        B4        )            where E denotes a set of errors, i denotes an element of set E, and li denotes an error position.
The syndrome polynomial and error locator polynomial σ (x) have the relation determined as shown below.σ(x)·S(x)≡ω(x)mod x2t  (B5)
In expression (B5), error evaluator polynomial ω (x) is a polynomial as written below.
                              ω          ⁡                      (            x            )                          =                              ∏                          i              ∈              E                                                                      ⁢                      e            ⁢                                                  ⁢                          i              ·                              α                                                      -                    1                                    ⁢                  i                                                      ⁢                                                            ∏                                      j                    =                    i                                                                    j                  ∈                  E                                                                                              ⁢                              (                                  x                  -                                      α                                                                  -                        1                                            ⁢                      j                                                                      )                                                                        (        B6        )            
Similarly, j denotes an element of set E and lj denotes an error position.
Alternatively, expression (B5) is written by an equivalent expression below.φ(x)x2t+σ(x)·S(x)=ω(x)  (B7)
Expression φ (x) is represented as follows.
                              ϕ          ⁡                      (            x            )                          =                              ∏                          i              ∈              E                                                                      ⁢                      e            ⁢                                                  ⁢                          i              ·                              α                                  1                  ⁢                                      i                    ·                    2                                    ⁢                  t                                                      ⁢                                                            ∏                                      j                    ≠                    i                                                                    j                  ∈                  E                                                                                              ⁢                              (                                  x                  -                                      α                                                                  -                        1                                            ⁢                      j                                                                      )                                                                        (        B8        )            
Euclidean decoding algorithm is a method of determining error locator polynomial σ (x) and error evaluator polynomial ω (x) based on relation (B7) above.
Specifically, when the number of errors is equal to t or less, error locator polynomial σ (x) and error evaluator polynomial ω (x) can uniquely be determined from expression (B7) by Euclidean algorithm to determine the greatest common divisor polynomial of x2t and S (x).
Brief description is given below concerning a procedure of determining error locator polynomial σ (x) and error evaluator polynomial ω (x) from expression (B7).
According to this procedure, polynomial σ (x) with degree t or lower and polynomial ω (x) with degree (t−1) or lower, which satisfy expression (B7) and are prime to each other, are determined.
Recurrence formula of polynomials Zi (x) is represented as shown below.Z−1(x)=x2t, Z0(x)=S(x)  (B9)
Based on expression (B9), polynomials Xi (x), Yi (x) and Zi (x) satisfying expression (B10) below are successively generated and this operation is repeated until Yi (x) has degree t or lower and Zi (x) has degree (t−1) or lower.Xi(x)Z−1(x)+Yi(x)Z0(x)=Zi(x)  (B10)
It can be proved that polynomials Yi (x) and Zi (x) thus generated correspond to error locator polynomial σ (x) and error evaluator polynomial ω (x), except for multiples of a constant. The following explanation assumes that such a correspondence is established.
Respective initial values of Xi (x) and Yi (x) are expressed as shown below.X−1(x)=1, X0(x)=0  (B11)Y−1(x)=0, Y0(x)=1  (B12)
For i=−1, 0, it is apparent that expression (B10) is satisfied.
However, since Z−1(x)=x2t is a polynomial of degree t or higher and the degree of S (x) is at least t as long as the number of errors is t or less, Z0 (x)=S (x) is a polynomial of degree t or higher. Therefore, Z−1 (x) and Z0 (x) are never error evaluator polynomial ω (x).
In the following process, the degree of Zi (x) is decreased with expression (B10) being satisfied.
It is assumed here that following expressions (B13) and (B14) are satisfied for i (≧1).Xi−2(x)Z−1(x)+Yi−2(x)Z0(x)=Zi−2(x)  (B13)Xi−1(x)Z−1(x)+Yi−1(x)Z0(x)=Zi−1(x)  (B14)
Zi−1(x) is lower in degree than Zi−2(x).
The degree can be lowered based on expressions (B13) and (B14). Zi−2 (x) is divided by Zi−1 (x) and the resultant quotient is here denoted by Qi (x). Members on both sides of expression (B14) are multiplied by Qi (x), and resultant products are subtracted from both members of expression (B13).
This corresponds to the following expressions in which Xi (x), Yi (x) and Zi (x) are represented as shown below based on expressions (B13) and (B14).Zi(x)=Zi−2(x)−Qi(x)Zi−1(x)  (B15)Xi(x)=Xi−2(x)−Qi(x)Xi−1(x)  (B16)Yi(x)=Yi−2(x)−Qi(x)Yi−1(x)  (B17)
If expressions (B13) and (B14) are satisfied, then expression (B10) is satisfied for polynomials Xi (x), Yi (x) and Zi (x) that satisfy expressions (B15) to (B17).
Zi (x) corresponds to the remainder determined by dividing Zi−2 (x) by Zi−1 (x), therefore, the degree thereof is lower than that of Zi−1 (x). The operation of expression (B15) is exactly the process of Euclidean algorithm to determine the greatest common divisor of x2t and S (x) in expression (B9).
FIG. 44 is a flowchart illustrating a flow of process for determining error locator polynomial ω (x) and error evaluator polynomial ω (x) by such Euclidean algorithm.
FIG. 44 shows a decoding algorithm for (182, 172, 11) RS code for example.
The Euclidean algorithm is applied for determining the greatest common divisor of expression x2t=x10 and syndrome polynomial S (x) below.S(x)=S9x9+S8x8+S7x7+S6x6+S5x5+S4x4+S3x3+S2x2+S1x1S0  (B18)
Referring to FIG. 44, calculation starts for determining error locator polynomial σ (x) and error evaluator polynomial ω (x) by Euclidean algorithm (step S10) and an initial value is set.
Variable R0i(i=0, 1, . . . , 10) is set as shown below corresponding to coefficient of x10.
R010=1, R0i=0(i=0, 1, . . . , 9)
Variable R1i (i=0, 1, . . . , 9) is set as below corresponding to coefficient of S (x).
R1i=Si (i=0, 1, . . . , 9)
Further, variables B0i, B1i (i=0, 1, . . . , 5) are set as below corresponding to respective coefficients of Y−1 (x) and Y0 (x).
B0i=0 (i=0, 1, . . . , 5)
B1i=0 (i=1, . . . , 5), B10=1
The initial setting is now completed. (step S12).
The degree of a polynomial having coefficient R0i is determined as N0 and the highest-degree coefficient of the polynomial is determined as Q0. Further, the degree of a polynomial having coefficient R1i is determined as N1 and the highest-degree coefficient of the polynomial is determined as Q1 (step S14).
N1 and 0 are compared (step S16). If N1=0, this process ends (step S30). If N1 is not equal to 0, the process proceeds to the next step.
After DN=N0−N1 operation, flag variable FN is set to 1 if DN<0 and to 0 if DN≧0 (step S18).
Flag variable FN and 0 are compared and the process proceeds to step S22 if FN=0 and to step S28 if FN=1 (step S20).
In step S20, the following operation is performed if FN=0.
R1i=Q0*R1(i−DN) (i=0, 1, . . . , 9)
R0i=Q1*R0i (i=0, 1, . . . , 9)
R110=0
B1i=Q0*B1(i−DN) (i=0, 1, . . . , 5)
B0i=Q1*B0i (i=0, 1, . . . , 5)
Operation * represents multiplication on an element on a Galois field. If (i−DN) is negative, 0 is assigned to R1i and B1i in the left side member (step S22).
The following operation is further performed on coefficients.
R0i=R0i exor R1i (i=0, 1, . . . , 9)
B0i=B0i exor B1i (i=0, 1, . . . , 5)
Operation exor represents exclusive-OR operation (step S24).
Decision is made on whether the degree of polynomial R0x expressed by variable R0i is equal to t (5 in this example) or lower (step S26). If the degree of polynomial R0x is equal to or lower than t, this process ends (step S30). If not, the process proceeds to step S28.
If FN=0 is not satisfied in step S20 or the degree of polynomial R0x is greater than t in step S26, values of variables R0i and R1i are exchanged with each other and values of variables B0i and B1i are exchanged with each other. After such exchange, the process returns to step S14 (step S28).
Calculation by Euclidean algorithm by another Reed-Solomon code or BCH code (Bose-Chaudhuri-Hpcquenghem code) in more general case is similarly done.
This calculation requires a multiplier of a Galois field dedicated to operation. “*”.
However, a problem here is the need of many multipliers for fast processing. In other words, although the greater number of multipliers increase the circuit size, an enhanced processing rate is achieved.
Reduction of the times multiplication is performed is also necessary, since power consumption increases if multiplication is carried out many times.
As an example, when the conventional circuit structure for implementing the Euclidean method discussed above employs one multiplier and the algorithm shown in FIG. 44 is followed therein, the circuit scale and throughput are estimated as below.
Number of multipliers: 1
Number of steps required for multiplication: 2×2t×2t
Number of times multiplication is performed: 2×2t×2t
A problem arises that, since the number of steps is proportional to the square of t, an increased t makes it impossible to enhance the processing rate.
Japanese Patent Laying-Open No. 1-276825 discloses a circuit structure for achieving fast calculation for such Euclidean method.
According to Japanese Patent Laying-Open No. 1-276825, speed enhancement of Euclidean calculation is accomplished by providing one multiplier per register.
For example, when the number of correctable errors is t, the minimum number of necessary registers is (2t+1). The circuit scale and throughput of the circuit structure disclosed in Japanese Patent Laying-Open No. 1-276825 are estimated as follows.
Number of multipliers: 2×(2t+1)
Number of steps required for multiplication: 2t
Number of times multiplication is performed: 2×2t×2t
Although speed enhancement is accomplished here, numerous multipliers are used and accordingly the circuit scale cannot be reduced.
Japanese Patent Laying-Open No. 10-65552 for example discloses another circuit structure for speedily performing such Euclidean calculation.
According to Japanese patent Laying-Open No. 10-65552, four multipliers are provided for example for improving the calculation speed in the Euclidean method.
For example, when the number of correctable errors is t, the circuit scale and throughput of the circuit structure disclosed in Japanese Patent Laying-Open No. 10-65552 are estimated as follows.
Number of multipliers: 4
Number of steps required for multiplication: 2t×2t
Number of times multiplication is performed: 2×2t×2t
Here again, since the number of steps is proportional to the square of t, the processing rate cannot be enhanced if the value of t increases.
In addition, power consumption is difficult to reduce in the conventional circuit structures discussed above due to the number of multiplying operations, i.e., 2×2t×2t.